package leetcode_day._2021._202103;

/**
 * @author yzh
 * @data 2021/3/30 21:00
 * 搜索二维矩阵
 * 思路：
 *   因为二维矩阵已经排序好了，所以可以使用二分查找
 *   先找出数字所在的行
 *   再找出数字所在的列
 */
public class _30_74 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        System.out.println(new _30_74().searchMatrix(matrix, 3));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = -1, r = matrix.length, c = matrix[0].length;
        int begin = 0, end = r - 1;
        while (begin <= end) {
            int middle = (begin + end) / 2;
            if (target >= matrix[middle][0] && target <= matrix[middle][c - 1]) {
                row = middle;
                break;
            }
            else if (target < matrix[middle][0]) end = middle - 1;
            else if (target > matrix[middle][c - 1]) begin = middle + 1;
        }
        if (row == -1) return false;
        begin = 0;
        end = c - 1;
        while (begin <= end) {
            int middle = (begin + end) / 2;
            if (target == matrix[row][middle]) return true;
            else if (target > matrix[row][middle]) begin = middle + 1;
            else end = middle - 1;
        }
        return false;
    }
}
